package com.lin.benchmade.pinyin;

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * 拼音切分器，分割用户输入的拼音，分割后匹配出对应的汉字.
 * 
 * @author xiaolin
 */
public final class LetterSpliter {
	private final static Logger LOG = LoggerFactory.getLogger(LetterSpliter.class);
	private final TrieNode rootNode;
	private static final String PATH_DIC = "/com/lin/benchmade/pinyin/PinYin.dic";
	private static final int POS_ARRAY_SIZE = 8;

	public LetterSpliter() {
		rootNode = new TrieNode();
		try {
			InputStream is = LetterSpliter.class.getResourceAsStream(PATH_DIC);
			InputStreamReader isr = new InputStreamReader(is);
			BufferedReader br = new BufferedReader(isr);
			String line;
			while ((line = br.readLine()) != null) {
				addNode(line);
			}
			br.close();
			isr.close();
			is.close();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	/**
	 * 添加一个String到树中.
	 * Date : 2012-11-14
	 * @param item 一个拼音
	 */
	private void addNode(String item) {
		TrieNode currentNode = rootNode;
		char[] charArray = item.toCharArray();
		for (short i = 0; i < charArray.length; i++) {
			currentNode = getOrCreateNode(charArray[i], currentNode, i == charArray.length - 1);
		}
	}

	/**
	 * 
	 * Date : 2012-11-14
	 * @param c 拼音中的一个char
	 * @param node 上级node
	 * @param isComplete 是不是终点节点
	 * @return	返回当前c所在的节点,不存在就创建
	 */
	private TrieNode getOrCreateNode(char c, TrieNode node, boolean isComplete) {
		TrieNode td = node.getChild().get(c);
		if (td == null) {
			td = new TrieNode(null, isComplete, c);
			node.getChild().put(c, td);
		} else if (isComplete && td.isComplete() == false) {
			td.setComplete(isComplete);
		}
		return td;
	}

	/**
	 * 将字母切分为拼音,按照最优方案切分.
	 * @param pinyin
	 * @return
	 */
	public List<BuildingBlock> split(String pinyin) {
		ArrayList<BuildingBlock> result = (ArrayList<BuildingBlock>) minGranularMatch(pinyin);
		/*按boost排序,第一位一定是得分最高,切分效果最好的*/
		Collections.sort(result);
		int maxBoost = Integer.MIN_VALUE;//最高分标识
		for (int i = 0; i < result.size(); i++) {
			//如果当前得分大于等于maxBoost,那么把当前值赋值给maxBoost.(等于 是为了有相同值的BuildingBlock能保留)
			if (result.get(i).getBoost() >= maxBoost) {
				maxBoost = result.get(i).getBoost();
			} else {
				//如果小于了maxBoost,说明从这以后的所有BuildingBlock都没有前面的好,全部删除(倒着删除)
				for (int j = result.size() - 1; j >= i; j--) {
					result.remove(j);
				}
				break;
			}
		}
		for (BuildingBlock bb : result) {
			LOG.debug(bb.toString() + "\t" + bb.boost);
		}
		return result;
	}

	private List<BuildingBlock> minGranularMatch(String keyWord) {
		List<BuildingBlock> result = new ArrayList<BuildingBlock>();

		char[] data = keyWord.toCharArray();
		short start = 0;
		DoubleArrayMap posInfos = new DoubleArrayMap();
		while (start < data.length) {
			byte[] depthsArray = matchMultiPos(data, start);
			if (depthsArray[0] == 0) {
				posInfos.put(start, 0);
				start += 1;
			} else {
				for (int i = 0; i < depthsArray[0]; i++) {
					posInfos.put(start, depthsArray[i + 1]);
				}
				start = depthsArray[1];
			}
		}
		pinyinAssembled(0, null, result, posInfos, data);
		return result;
	}

	/**
	 * 一个拆分后的term序列.使用parent - child 模式进行迭代循环,每次循环后得到一个新的,完整的序列.
	 * Date : 2012-11-14
	 * @param startPos 起始位置.
	 * @param father 父集合.
	 * @param result 最终返回集合.
	 * @param posInfos	存储parent - child关系的一个类似map的结构.
	 * @param data	数据源,即要切分的字符串.因为posInfos 没有存储字符信息,只有位置.所以还要到data中得到char.
	 */
	private void pinyinAssembled(int startPos, BuildingBlock father, List<BuildingBlock> result, DoubleArrayMap posInfos, char[] data) {
		if (startPos < data.length) {
			byte[] endPos = posInfos.get(startPos);
			int intelvel;
			boolean isPinyin;
			for (int cursor = 1; cursor < endPos[0]; cursor++) {
				isPinyin = endPos[cursor] > 0;
				//if(isComplete){ //加上这个条件 即只有全拼的才能返回
				//ArrayList<PinYinBean> child = (ArrayList<PinYinBean>) ((ArrayList) list).clone();
				BuildingBlock bblock = new BuildingBlock(father);
				intelvel = isPinyin ? endPos[cursor] : startPos + 1;
				char[] pyCharArray = new char[intelvel - startPos];
				System.arraycopy(data, startPos, pyCharArray, 0, intelvel - startPos);
				bblock.add(new PinYinBean(pyCharArray, isPinyin));
				/*  只有符合条件的,才能进行迭代,如果没有进入到下面的if,那么也不会进入最后面的else中添加,这个子序列会被抛弃,
					直到能走到startPos < data.length = false时,才能进入到else中,最终添加到result
				*/
				if (bblock.isValid()) {
					pinyinAssembled(intelvel, bblock, result, posInfos, data);
				}
				//}
			}
		} else {
			//到达了letter的结尾,计算该BuildingBlock的权重.用来最终判断这个BuildingBlock是否应该返回
			father.computBoost();
			result.add(father);
		}
	}

	private byte[] matchMultiPos(char[] data, short offset) {
		byte[] array = new byte[POS_ARRAY_SIZE];
		return matchMultiPos(rootNode, data, offset, array, (byte) 1);
	}

	/**
	 * 
	 * Date : 2012-11-21
	 * @param node	从根节点开始,每次迭代传入当前字符所在节点.
	 * @param data	完整的字符串转化的char数组.
	 * @param offset	偏移量,每次从data的第几个位置开始匹配.
	 * @param endPos	最终搜集完整拼音集合的数组,放入的数据为拼音的结束位置,第一个元素是这个数组的有效数据长度[3, 2, 3, 4, 0, 0, 0, 0].
	 * @param posCursor		endPos的位置游标,每当有一个isComplete,posCursor就自增一个.
	 * @return
	 */
	private byte[] matchMultiPos(TrieNode node, char[] data, int offset, byte[] endPos, byte posCursor) {
		TrieNode childNode = node.getChild().get(data[offset]);
		if (childNode != null) {
			if (data.length - offset > 1) {
				if (childNode.isComplete()) {// 如果走到一颗树的节点，赋值给pos，因为最大匹配，所以还要往下走，用pos记录下当前位置，如果以后没有匹配上，则取这个位置
					endPos[posCursor] = (byte) (offset + 1);
					endPos[0] = posCursor;
					posCursor += 1;
				}
				endPos = matchMultiPos(childNode, data, offset + 1, endPos, posCursor);
			} else {
				endPos[posCursor] = (byte) data.length;// 如果走到树的尽头，char数组也走到尽头，但是还没匹配上，那么说明这个是一个合法的前缀，位置设置为最后一个，用-1做一个特殊标示
				endPos[0] = posCursor;
			}
		}
		return endPos;
	}

	/**
	 * Trie的节点类.之前所有的添加等操作放到Trie中进行,这这次抽取出来后,Trie的操作都提取出来了,存储的信息用TrieNode.
	 * @Author : xiaolin
	 * @Date : 2012-11-14 下午5:29:04
	 */
	static class TrieNode {

		private Map<Character, TrieNode> child;
		private boolean isComplete;
		private Character charVal;

		public TrieNode(Map<Character, TrieNode> child, boolean isComplete, char charVal) {
			this.child = child;
			this.isComplete = isComplete;
			this.charVal = charVal;
		}

		public TrieNode() {
		}

		public Map<Character, TrieNode> getChild() {
			if (child == null) {
				child = new HashMap<Character, TrieNode>();
			}
			return child;
		}

		public boolean isComplete() {
			return isComplete;
		}

		public void setComplete(boolean isComplete) {
			this.isComplete = isComplete;
		}

		public void setCharVal(Character charVal) {
			this.charVal = charVal;
		}

		public Character getCharVal() {
			return charVal;
		}
	}

	/**
	 * 为拼接ArrayList创建的新类.同时增加了一些判断的逻辑,简化调用.
	 * @Author : xiaolin
	 * @Date : 2012-11-14 下午5:30:31
	 */
	public static class BuildingBlock implements Comparable<BuildingBlock> {
		private final ArrayList<PinYinBean> items;
		private boolean isEentirely = true; //是不是全是全拼拼音
		private boolean valid = true;
		private int boost = 0; //add 2012-11-21 xiaolin

		public BuildingBlock() {
			items = new ArrayList<PinYinBean>();
		}

		/**
		 * 构造一个新的list,数据由传递过来的parent集合得到,使用clone节省开销.
		 * Date : 2012-11-14
		 * @param father
		 */
		public BuildingBlock(BuildingBlock father) {
			if (father == null) {
				items = new ArrayList<PinYinBean>();
			} else {
				items = (ArrayList<PinYinBean>) father.items.clone();
				isEentirely = father.isEentirely;
			}

		}

		public boolean isValid() {
			return valid;
		}

		public int size() {
			return items.size();
		}

		public ArrayList<PinYinBean> getData() {
			return items;
		}

		/**
		 * 添加一个拼音,同时判断添加的这个拼音是否合法,如果非法,调用端将放弃该序列.
		 * Date : 2012-11-21
		 * @param p 一个PinYinBean
		 */
		public void add(PinYinBean p) {
			items.add(p);
			isEentirely = isEentirely & p.isComplete(); //按位与是为了 只要有一个false.整个都为false
			//判断是不是有违法的字符.不可能有汉字是以u和v开始的,所以如果含有这2个字符,那么直接去除.
			if (!p.isComplete() && p.getPinyin().length == 1 && isValidChar(p.getPinyin()[0])) {
				valid = false;
			}
		}

		private boolean isValidChar(char c) {
			return c == 'u' || c == 'v';
		}

		public boolean isEentirely() {
			return isEentirely;
		}

		@Override
		public int compareTo(BuildingBlock o) {
			return o.boost - this.boost;
		}

		public int getBoost() {
			return boost;
		}

		/**
		 * 计算BuildingBlock权重,都是全拼,并且每个拼音长度都大于1,那么起始值是100
		 * 如果含有简拼,起始值是0,
		 * 如果全拼中有一个单字的拼音,那么剪掉4,这个4是因为一个拼音最长是5,减去4是个随意值.
		 * 如果是简拼,那么减去整个序列的长度,长度越短,值越大,能够区分混拼中含有全拼的稍好一点的序列.
		 * Date : 2012-11-21
		 */
		public void computBoost() {
			boost = isEentirely ? 100 : 0;
			for (PinYinBean p : items) {
				if (p.getPinyin().length == 1) {
					boost -= 4;
				}
			}
		}

		@Override
		public String toString() {
			StringBuilder sb = new StringBuilder();
			sb.append(isEentirely).append(": ");
			for (PinYinBean p : items) {
				if (p.isComplete()) {
					sb.append("+");
				}
				sb.append(String.valueOf(p.getPinyin())).append(" ");
			}
			return sb.toString();
		}

	}

	public static void main(String[] args) {

		LetterSpliter n = new LetterSpliter();
		List<BuildingBlock> list = n.split("jianguo");
		for (BuildingBlock l : list) {
			System.out.println(l.toString());
		}
	}
}

/**
 * 拆分拼音后的Term位置信息,通过位置信息的start和end信息,得到哪些term能够组成一个完整的拼音序列.
 * @Author : xiaolin
 * @Date : 2012-11-14 下午5:44:16
 */
final class DoubleArrayMap {
	private int[] keyArray, valueArray;
	private int cursor = 0;
	private final int DEFAULT_INIT_SIZE = 16;
	private int maxSize = DEFAULT_INIT_SIZE;

	public DoubleArrayMap() {
		keyArray = new int[DEFAULT_INIT_SIZE];
		valueArray = new int[DEFAULT_INIT_SIZE];
	}

	public DoubleArrayMap(int initSize) {
		keyArray = new int[initSize];
		valueArray = new int[initSize];
		maxSize = initSize;
	}

	/**
	 * 线程不安全版本.2个线程同时等待扩容,同时解锁进入赋值区域后,会覆盖一个值.
	 * Date : 2012-11-27
	 * @param key	词的起始位置
	 * @param value	词的结束位置
	 */
	public void put(int key, int value) {
		checkSize();
		keyArray[cursor] = key;
		valueArray[cursor] = value;
		cursor++;
	}

	/**
	 * 检查数组是否使用完,如果都已经被使用,扩充一倍的大小.
	 * Date : 2012-11-14
	 */
	private void checkSize() {
		if (cursor >= maxSize) {
			maxSize = maxSize * 2;
			keyArray = Arrays.copyOf(keyArray, maxSize);
			valueArray = Arrays.copyOf(valueArray, maxSize);
		}
	}

	/**
	 * 位置信息不会有太长的数据,所以使用byte存储位置信息.
	 * Date : 2012-11-14
	 * @param key
	 * @return
	 */
	public byte[] get(int key) {
		byte[] values = new byte[6];
		int pos = 1;
		for (int i = 0; i < cursor; i++) {
			if (keyArray[i] == key) {
				values[pos++] = (byte) valueArray[i];
			}
		}
		values[0] = (byte) pos;//byte[]的头上是一共有多少个元素,因为之前++, 所以注意循环的时候从1开始   i<values[0]
		return values;
	}
}
